package com.cat.chapter049;

/**
 * @author cat
 * @description https://leetcode.cn/problems/replace-the-substring-for-balanced-string/description/
 * @create 2025/7/19 15:22
 * @since JDK17
 */

public class Solution05 {
    public int balancedString(String str) {
        int n = str.length(), ans = Integer.MAX_VALUE, debt = 0;
        int[] s = new int[n], cnt = new int[4];
        for (int i = 0; i < n; i++) {   //
            char c = str.charAt(i);
            s[i] = c == 'Q' ? 0 : c == 'W' ? 1 : c == 'E' ? 2 : 3;
            cnt[s[i]]++;
        }

        for (int i = 0; i < 4; i++) {
            if (cnt[i] < n / 4) {
                cnt[i] = 0;
            } else {
                cnt[i] = n / 4 - cnt[i];    // 欠这么多个
                debt += cnt[i];
            }
        }

        if (debt == 0) {
            return 0;
        }

        for (int l = 0, r = 0; r < n; r++) {
            if (cnt[s[r]]++ < 0) {
                debt++; // 还一个
            }

            if (debt == 0) {
                while (cnt[s[l]] > 0) {
                    cnt[s[l++]]--;
                }
                if (ans > r - l + 1) {
                    ans = r - l + 1;
                }
            }
        }

        return ans;
    }
}
